1. Field of the Invention
The present invention relates to telecommunications, particularly, to a system and method for improved signal reception, and more particularly to a system and method for improved maximum likelihood sequence detection.
2. Background and Objects of the Present Invention
The evolution of wireless communication over the past century, since Guglielmo Marconi's 1897 demonstration of radio's ability to provide continuous contact with ships sailing the English Channel, has been remarkable. Since Marconi's discovery, new wireline and wireless communication methods, services and standards have been adopted by people throughout the world. This evolution has been accelerating, particularly over the last ten years, during which time the mobile radio communications industry has grown by orders of magnitude, fueled by numerous technological advances that have made portable radio equipment smaller, cheaper and more reliable. The exponential growth of mobile telephony will continue to rise in the coming decades as well, as this wireless network interacts with and eventually overtakes the existing wireline networks.
One technical difficulty encountered in wireless telephonic communications is signal distortion. For example, on top of additive white Gaussian noise (AWGN) the signal is subject to multipath fading. A propagation delay is caused by the multiple propagation paths to a receiver due to buildings or terrain. As a result of time delays across the different paths, a succession of discrete pulses representing symbols transmitted across a communications channel are smeared to the point that they are no longer distinguishable as well-defined pulses at the receiving terminal. Instead, the received symbols overlap somewhat causing intersymbol interference (ISI).
With reference to FIG. 1, there is illustrated a mathematical model of ISI. This is a filter of order L+1, where `L` is the number of memory elements in the filter and L+1 is the number of filter coefficients (.theta..sub.0, . . . .theta..sub.L) . In particular, a symbol stream of discrete symbols s.sub.k, each a member of a defined and finite alphabet A.backslash. forwarded to a given channel of a transmitter 10 having channel coefficients .theta. combined therein and transmitted. Along the transmission route 12 to a receiver 14 shown in the figure, a noise component n.sub.k is added, represented by an adder 16, altering the symbol stream signal into a different one, e.g., v.sub.k, received by the receiver 14.
The process of undoing the effects of ISI is referred to as equalization. To assist in equalizing the aforementioned altered symbol stream received at the receiver 14, digital telecommunications standards employing Time Division Multiple Access (TDMA) technology, like that of the Global System for Mobile communications (GSM) and the IS-136 standards, employ training or synchronization sequences to facilitate signal demodulation. For example, in GSM, systems employ time slots to transmit a 156.25-bit message, where 22 or more of those bits are utilized in training for channel equalization. It should be understood that synchronization is absolutely necessary in certain circumstances, i.e., to initially align the receiver 14 with the transmitter's 10 signal. In conventional systems even after such synchronization occurs, i.e., after establishing timeslot alignment, there is still a need for the training bits in each timeslot. It should be apparent, however, that by minimizing or eliminating the use of these equalization training bits in each time slot, particularly after synchronization has been achieved, this would dramatically increase the information throughput without significant changes to the protocol. In any event, the GSM system utilizes the aforementioned 22 bits as training bits throughout all timeslots of the transmission.
Through use of the training bits, ISI is corrected in current systems by using the training bits for channel equalization, i.e., ascertaining the aforementioned channel coefficients .theta. for that communications route or link 12 and modifying (demodulating) the incoming signal in accordance with these coefficients. As a result of the dispersive nature of channels across the time domain due to the noise n.sub.k, each channel coefficient .theta. is multiplied with the incoming information, i.e., symbols. It should be understood to those skilled in the art that, with a channel behaving as a filter, the phenomenon of ISI may itself also be modeled as a filter. The length of the filter is the extent of ISI, and is denoted by `L+1`. Accordingly, in a situation where there is no ISI, the channel may be modeled with a single non-zero channel coefficient, where all other coefficients are zero, e.g., 1,0,0. In this example, channel coefficients characterize the behavior of the channel. Assuming L=2, then with ISI, all of the remaining channel coefficients are non-zero also, e.g., 1, 0.5, 0.2.
Accordingly, a receiver 14 must demodulate the incoming symbol stream, v.sub.k, and overcome both the signal dispersion and the background noise present (AWGN). With the conventional channel equalization technique, both ISI and AWGN are overcome by use of the aforementioned training sequence bits. As discussed, having knowledge of a transmission result, i.e., the known training sequence value, one may ascertain what the channel did to the outgoing signal and demodulate the received signal into the appropriate symbols accordingly.
A well-known symbol estimation/detection technique employed to perform maximum likelihood sequence estimation (MLSE) on the input symbol stream is the Viterbi algorithm, which dynamically estimates the most probable sequence of data symbols by maximizing a likelihood function describing the received signal. In general, for a binary system attempting to decipher an N-bit input symbol string, a brute force approach (2.sup.N) is computationally infeasible, i.e., it is of exponential order. It should be understood, of course, that for an alphabet of size M, M.sup.N comparisons are required.
The Viterbi algorithm greatly simplifies this exponential order analysis by focusing on a discrete sequence of candidate symbols stored within L memory elements of the filter, i.e., L symbols in length. As an example, for N=156 bits, representing a time burst's binary data information or symbol content, L may be as low as 2, where bounding the analysis to 4 states (2.sup.2) is preferred. With the two binary values conventionally represented by +1 and -1, these four states of the filter memory elements are as follows:
______________________________________ States ______________________________________ -1, -1 -1, +1 +1, -1 +1, +1 ______________________________________
In the dynamic programming approach described by the Viterbi algorithm, the incremental shortest path for each state is ascertained, maximizing the likelihood function linearly.
The Viterbi algorithm, although currently the technique of choice in the sequence analysis art, primarily for its linear order computational simplicity, nonetheless has its shortcomings. For instance, the Viterbi algorithm requires foreknowledge of the channel and its coefficients, which in the wireless environment are constantly changing due to channel fading, propagation delays and other signal interference conditions. To adaptively equalize the signal from timeslot to timeslot, the Viterbi algorithm therefore requires the aforementioned training bits, which provide the requisite channel coefficient information enabling the receiver to demodulate the signal dynamically.
Although the Viterbi algorithm operates best in situations where the channel coefficients are known, in "blind" equalization, i.e., where there is no foreknowledge of the channel coefficients and the algorithm must adapt itself to the conditions present, utilizations of the Viterbi algorithm have proved suboptimal. It should, therefore, be understood that by requiring foreknowledge of the channel coefficients Viterbi algorithms are not well suited for a self-adaptive sequence detection technique, particularly in the blind equalization context, and alternative methodologies are required in such instances. One such alternative, the Fano algorithm, although conventionally used primarily in the context of convolutional code decoding, is set forth and utilized in the present invention. Another alternative, the stack algorithm, is also described.
It is, accordingly, apparent that dynamic programming techniques, such as those utilizing Viterbi algorithms, are infeasible for implementing sequential self-adaptive equalization techniques.
It is, therefore, an object of the present invention to provide an improved maximum likelihood sequence estimation/detection technique and methodology for implementing self-adaptive equalization.
It is a further object of the present invention that the aforesaid improved technique determine the transmitted symbol sequence without using a training sequence to estimate the channel coefficient parameters that are used to model the unknown intersymbol interference (ISI).
It is also an object of the present invention that the improved technique employ recursive techniques.